import java.util.ArrayList;
import java.util.Collections;
import java.util.Enumeration;

public class OctreeNode {
	
	private OctreeNode[] children = null;
	private ArrayList<Primitive> primitivs = null;
	private OctreeNode parent = null;
	private Vector lowest = null;
	private Vector highest = null;
	
	private int dbgDepth;
	private static int dbgCheckDepth = 1;
	private static int dbgCounter = 0;
	
	private static double minBoxVolume = 0.1;
	
	public static ArrayList<Primitive> dbgBoxForNodes = new ArrayList<Primitive>();
	
	
	private OctreeNode(){
		primitivs = new ArrayList<Primitive>();
	}
	
	private OctreeNode(Vector lowest , Vector highest){
		this();
		this.lowest = lowest;
		this.highest = highest;
	}
	
	public PrimAndPoint findIntersection(Vector origin, Vector direction ){
		Vector boxOrigin;
		PrimAndPoint intersectionPAP;
		if (!isPointInBox(this.lowest, this.highest, origin)){
			boxOrigin = getInsidePoint(origin, direction);
			if (!isPointInBox(this.lowest, this.highest, boxOrigin)) return null;
		}else{
			boxOrigin = origin;
		}
		OctreeNode leaf = this.findRelevantLeaf(boxOrigin, direction);
		while (true) {
			intersectionPAP = leaf.shootRayInsideNode(boxOrigin, direction);
			if (intersectionPAP.point != null) return intersectionPAP;
			leaf = leaf.changeLeaf(origin, direction)
		}
		
		
		
		return new Box();
		
	}
	
	private PrimAndPoint shootRayInsideNode(Vector origin, Vector direction){
		
		Enumeration<Primitive> e = Collections.enumeration(this.primitivs);
		Primitive p;
		double shortestDist_Q = Double.MAX_VALUE;
		double dist_Q;
		Primitive closestP = null;
		Vector closestV = null;
		Vector temp = null;
		
		while(e.hasMoreElements()){
		     p = e.nextElement();
		     temp = p.intersectionPoint_direction(origin, direction);
		     if (temp == null) 
		    	 continue;
		     dist_Q = Vector.getDistance_Q(temp, origin);
		     if (dist_Q < shortestDist_Q){
		    	 shortestDist_Q = dist_Q;
		    	 closestP = p;
		    	 closestV = temp;
		     }
		}
		return new PrimAndPoint(closestP, closestV);
	}
	
	private OctreeNode findRelevantLeaf( Vector origin, Vector direction){
		if (parent.isLeaf())return parent;
		for (int i=0; i<8; i++){
			if (isPointInBox(children[i].lowest, children[i].highest, origin)){
				return children[i].findRelevantLeaf(origin, direction); 
			}
		}
		return null;
		
	}
	
	private boolean isLeaf(){
		return (children == null);
	}
	private Vector getInsidePoint(Vector origin, Vector direction){
		double[] co = origin.getCoords();
		double[] cd = direction.getCoords();
		double[] cRoot = this.highest.getCoords();
		double var = (cRoot[0] - co[0])/cd[0];
		Vector maybeInsidePoint = Vector.add(origin, direction).mul(var);
		return maybeInsidePoint;
	}
	

	
	public static OctreeNode buildOctree( ArrayList<Primitive> primArr){
		System.out.println(dbgCounter);
		dbgCounter++;
		OctreeNode root = new OctreeNode();
		root.lowest = getLowestVector(primArr);
		root.highest = getHighestVector(primArr);
		root.primitivs = primArr;
		root.dbgDepth = 0;
		buildOctreeChildren(root);
		nodeToBox(root);
		return root;
	}
	
	private static OctreeNode recursiveBuildOctree(OctreeNode parent, Vector lowest, Vector highest){
		System.out.println(lowest.print() + "  " + highest.print());
		System.out.println(dbgCounter);
		dbgCounter++;
		ArrayList<Primitive> parentPrimList = parent.primitivs;
		OctreeNode ret = new OctreeNode();
		ret.lowest = lowest;
		ret.highest = highest;
		ret.parent = parent;
		Enumeration<Primitive> e = Collections.enumeration(parentPrimList);
		Primitive p;
		Vector pLow, pHigh;
		while(e.hasMoreElements()){
		     p = e.nextElement();
		     pLow = p.getLowestPoint();
		     pHigh = p.getHighestPoint();
		     if (doBoxesIntersect(pLow, pHigh, lowest, highest)){
		    	 ret.primitivs.add(p);
		     }
		}
		ret.dbgDepth = parent.dbgDepth + 1;
		buildOctreeChildren(ret);		
		nodeToBox(ret);
		return ret;	
	}
	
	private static void buildOctreeChildren(OctreeNode parent){
		
		//if (parent.dbgDepth > 0) return;
		
		double[] cl = parent.lowest.getCoords();
		double[] ch = parent.highest.getCoords();
		if (parent.primitivs.size() > 1){
			if (calcVolume(parent.lowest, parent.highest) > minBoxVolume){
				
				parent.children = new OctreeNode[8];			
				OctreeNode child;
				
				// x is right, y is up, z is front
				
				//0.  right-top-front (+, +, +)
				child = recursiveBuildOctree(parent, 
						new Vector((ch[0]+cl[0])/2, (ch[1]+cl[1])/2, (ch[2]+cl[2])/2), 
						parent.highest);
				parent.children[0] = child;
				
				//1.  left-top-front (-,+,+)
				child = recursiveBuildOctree(parent, 
						new Vector(cl[0], (ch[1]+cl[1])/2, (ch[2]+cl[2])/2), 
						new Vector((ch[0]+cl[0])/2, ch[1], ch[2]));
				parent.children[1] = child;
				
				//2.  right-buttom-front (+,-,+)
				child = recursiveBuildOctree(parent, 
						new Vector((ch[0]+cl[0])/2, cl[1], (ch[2]+cl[2])/2), 
						new Vector(ch[0], (ch[1]+cl[1])/2, ch[2]));
				parent.children[2] = child;
				
				//3.  left-buttom-front (-,-,+)
				child = recursiveBuildOctree(parent,
						new Vector(cl[0], cl[1], (ch[2]+cl[2])/2), 
						new Vector((ch[0]+cl[0])/2, (ch[1]+cl[1])/2, ch[2]));
				parent.children[3] = child;
				
				//4.  right-top-back (+,+,-)
				child = recursiveBuildOctree(parent, 
						new Vector((ch[0]+cl[0])/2, (ch[1]+cl[1])/2, cl[2]), 
						new Vector(ch[0], ch[1], (ch[2]+cl[2])/2));
				parent.children[4] = child;
				
				//5.  left-top-back (-,+,-)
				child = recursiveBuildOctree(parent,
						new Vector(cl[0], (ch[1]+cl[1])/2, cl[2]),
						new Vector((ch[0]+cl[0])/2, ch[1], (ch[2]+cl[2])/2));
				parent.children[5] = child;
				
				//6.  right-buttom-back (+,-,-)
				child = recursiveBuildOctree(parent,
						new Vector((ch[0]+cl[0])/2, cl[1], cl[2]),
						new Vector(ch[0] , (ch[1]+cl[1])/2, (ch[2]+cl[2])/2));
				parent.children[6] = child;
								
				//7.  left-buttom-back (-,-,-)
				child = recursiveBuildOctree(parent, 
						parent.lowest, 
						new Vector((ch[0]+cl[0])/2, (ch[1]+cl[1])/2, (ch[2]+cl[2])/2));
				parent.children[7] = child;
					
			}
		}
	}
	
	private static void nodeToBox(OctreeNode n){
		if (n.dbgDepth != dbgCheckDepth) return;
		double[] cl = n.lowest.getCoords();
		double[] ch = n.highest.getCoords();
		Vector p0 = n.lowest;
		Vector p1 = new Vector(cl[0], cl[1], ch[2]);
		Vector p2 = new Vector(cl[0], ch[1], cl[2]);
		Vector p3 = new Vector(ch[0], cl[1], cl[2]);
		Box b = new Box(p0, p1, p2, p3);
		b.setMtlDiffuse(new RGB(Math.random(),Math.random(),Math.random()));
		dbgBoxForNodes.add(b);
	}
	
	
	private static double calcVolume( Vector low, Vector high){
		double[] cl = low.getCoords();
		double[] ch = high.getCoords();
		double volume = (ch[0] - cl[0])*(ch[1] - cl[1])*(ch[2] - cl[2]); 
		System.out.println(volume);
		return volume;
	}
	
	private static Vector getLowestVector(ArrayList<Primitive> primArr){
		Enumeration<Primitive> e = Collections.enumeration(primArr);
		Primitive p;
		double[] lowestYet = {Double.MAX_VALUE, Double.MAX_VALUE, Double.MAX_VALUE};
		double[] temp = null;
		while(e.hasMoreElements()){
		     p = e.nextElement();
		     temp = (p.getLowestPoint()).getCoords();
		     for(int i=0 ; i<3; i++){
		    	 lowestYet[i] = Math.min(lowestYet[i],temp[i]); 
		     }	     
		}
		return new Vector(lowestYet[0], lowestYet[1], lowestYet[2]);
	}
	
	private static Vector getHighestVector(ArrayList<Primitive> primArr){
		Enumeration<Primitive> e = Collections.enumeration(primArr);
		Primitive p;
		double[] lowestYet = {Double.MIN_VALUE, Double.MIN_VALUE, Double.MIN_VALUE};
		double[] temp = null;
		while(e.hasMoreElements()){
		     p = e.nextElement();
		     temp = (p.getHighestPoint()).getCoords();
		     for(int i=0 ; i<3; i++){
		    	 lowestYet[i] = Math.max(lowestYet[i],temp[i]); 
		     }	     
		}
		return new Vector(lowestYet[0], lowestYet[1], lowestYet[2]);
	}
	
	private static boolean doBoxesIntersect(Vector Alow, Vector Ahigh, Vector Blow, Vector Bhigh){
		return isBoxInBox(Alow, Ahigh, Blow, Bhigh) || isBoxInBox(Blow, Bhigh, Alow, Ahigh);
	}
	
	private static boolean isBoxInBox(Vector outerBoxL, Vector outerBoxH, Vector innerBoxL, Vector innerBoxH){
		double[] cIL = innerBoxL.getCoords();
		double[] cIH = innerBoxH.getCoords();
		
		if ( isPointInBox(outerBoxL, outerBoxH, new Vector(cIL[0], cIL[1], cIL[2]))) return true;
		if ( isPointInBox(outerBoxL, outerBoxH, new Vector(cIL[0], cIL[1], cIH[2]))) return true;
		
		if ( isPointInBox(outerBoxL, outerBoxH, new Vector(cIL[0], cIH[1], cIL[2]))) return true;
		if ( isPointInBox(outerBoxL, outerBoxH, new Vector(cIL[0], cIH[1], cIH[2]))) return true;
		
		if ( isPointInBox(outerBoxL, outerBoxH, new Vector(cIH[0], cIL[1], cIL[2]))) return true;
		if ( isPointInBox(outerBoxL, outerBoxH, new Vector(cIH[0], cIL[1], cIH[2]))) return true;
		
		if ( isPointInBox(outerBoxL, outerBoxH, new Vector(cIL[0], cIH[1], cIH[2]))) return true;
		if ( isPointInBox(outerBoxL, outerBoxH, new Vector(cIH[0], cIH[1], cIH[2]))) return true;
		
		return false;
	}
	
	private static boolean isPointInBox(Vector boxLow, Vector boxHigh, Vector p){
		double[] cbl = boxLow.getCoords();
		double[] cbh = boxHigh.getCoords();
		double[] cp = p.getCoords();
		for (int i=0; i<3; i++){
			if ( (cbl[i] >= cp[i]) || 
					(cbh[i] <= cp[i]) ){
				return false;
			}
		}
		return true;
	}
	

}
